/**
 * 19. 删除链表的倒数第N个节点
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 */
public class Solutions_19 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        int n = 2;  // {1, 2, 3, 5}
//        int n = 5;  // {2, 3, 4, 5}

        ListNode result = removeNthFromEnd(head, n);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解题思路：
     * 删除操作，本质上就是修改删除结点的前一结点，将前一结点的下一结点指向为要删除结点的下一结点
     * 关键：找到要删除结点的前一结点，而不是要删除的结点
     */
//    public static ListNode removeNthFromEnd(ListNode head, int n) {
//        // 快慢指针
//        ListNode fast = head, slow = head;
//        // 快指针先走 n + 1 步
//        for (int i = 0; i <= n; i++) {
//            fast = fast.next;
//        }
//        // 快慢指针一起走，直到快指针走完（指向 null）
//        while (fast != null) {
//            fast = fast.next;
//            slow = slow.next;
//        }
//        // 快指针指向 null 时，慢指针所在，就是要删除结点的前一结点
//        slow.next = slow.next.next;
//        return head;
//    }

    /**
     * 计算长度后，遍历
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int size = MyLinkedListUtils.size(head);
        if (n == size) {
            // 要删除的是头结点
            return head.next;
        }
        ListNode cur = head;
        // 要求删除倒数第 n 个结点，那么先遍历找到倒数第 n + 1 个结点
        while (size - 1 > n) {
            cur = cur.next;
            size --;
        }
        // 给定的 n 保证是有效的，所以不用判断
        cur.next = cur.next.next;
        return head;
    }

    /**
     * 快慢指针，一次遍历
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        // 以上代码，在删除正序的第一个结点时，会出现空指针
        // 创建一个虚拟头(哑)结点，来保证第一个结点，也有其前驱结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 快慢指针
        ListNode fast = dummy, slow = dummy;
        // 快指针先走 n + 1 步
        for (int i = 0; i <= n; i++) {
            // 给定的 n 保证是有效的，所以不用判断
            fast = fast.next;
        }
        // 快慢指针一起走，直到快指针走完（指向 null）
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 快指针指向 null 时，慢指针所在，就是要删除结点的前一结点
        slow.next = slow.next.next;
        return dummy.next;
    }
}
